# 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
#
# 示例 1:
#  输入: nums = [-1,0,3,5,9,12], target = 9
# 输出: 4
# 解释: 9 出现在 nums 中并且下标为 4
#
# 示例 2:
# 输入: nums = [-1,0,3,5,9,12], target = 2
# 输出: -1
# 解释: 2 不存在 nums 中因此返回 -1
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def searchByRecursion(start, end) -> int:  # 递归实现
            if start > end or nums[start] > target or nums[end] < target:  # 当二分到最后没有元素了，说明不存在
                return -1
            mid = start + (end - start) // 2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                return searchByRecursion(mid + 1, end)
            else:
                return searchByRecursion(start, mid - 1)

        def searchByIteration() -> int:  # 迭代实现
            left, right = 0, len(nums) - 1
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1
            return -1
        return searchByIteration()
        # return searchByRecursion(0, len(nums) - 1)


if __name__ == '__main__':
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9
    print(Solution().search(nums, target))
